import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;

import org.junit.Test;



public class MyTest {
/*     int count=0;
    public int triangleNumber(int[] nums) {
        traceBack(nums, 0, new ArrayList<Integer>());
        return count;
    }
    private void traceBack(int[] nums,int idx,List<Integer> list){
        if(list.size()==3){
            int a=list.get(0);
            int b=list.get(1);
            int c=list.get(2);
            if(a+b>c&&a+c>b&&b+c>a){
                count++;
                //System.out.println(a+" "+b+" "+c+" ");
            }
            return;
        }
        for(int i=idx;i<nums.length;i++){
            list.add(nums[i]);
            traceBack(nums, i+1, list);
            list.remove(list.size()-1);
        }
    } */

    public int triangleNumber(int[] nums) {
        int count=0;
        Arrays.sort(nums);
        for(int i=0;i<nums.length;i++){            
            for(int j=i+1;j<nums.length-1;j++){
                int k=j+1;
                while(k<nums.length){
                    if(nums[i]+nums[j]>nums[k]){
                        count++;
                        k++;
                    }else{
                        break;
                    }
                }               
            }
        }
        return count;
    }

    public int lengthOfLongestSubstring(String s) {
        if(s.length()==0){
            return 0;
        }
        HashSet<Character> hashSet=new HashSet<Character>();
        int head=0,rear=1;
        int maxLength=0;
        hashSet.add(s.charAt(0));
        while(rear<s.length()){
            char c=s.charAt(rear);
            if(!hashSet.contains(c)){
                hashSet.add(c);
                rear++;
                maxLength=Math.max(maxLength, rear-head);
            }else{
                while(hashSet.contains(c)){
                    hashSet.remove(s.charAt(head));
                    head++;
                }
            }
        }
        maxLength=Math.max(maxLength, rear-head);
        return maxLength;
    }

    public boolean checkInclusion(String s1, String s2) {
        if(s1.length()>s2.length()){
            return false;
        }
        int[] counts1=new int[26];
        int[] counts2=new int[26];
        for(int i=0;i<s1.length();i++){
            counts1[s1.charAt(i)-'a']++;
            counts2[s2.charAt(i)-'a']++;
        }
        if(Arrays.equals(counts1, counts2)){
            return true;
        }
        int head=0;
        int rear=s1.length()-1;
        while(rear<s2.length()-1){
            counts2[s2.charAt(head)-'a']--;
            head++;
            rear++;
            counts2[s2.charAt(rear)-'a']++;
            if(Arrays.equals(counts1, counts2)){
                return true;
            }
        }
        return false;
    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        TreeNode root=new TreeNode();
        VLR(root, preorder, 0, preorder.length-1, inorder, 0, inorder.length-1, true);
        return root.right;
    }
    private void VLR(TreeNode root,int[] preorder,int i,int j, int[] inorder,int x,int y,boolean isRight){
        if(i>j){
            return;
        }
        TreeNode node= new TreeNode(preorder[i]);
        if(isRight){
            root.right=node;
        }else{
            root.left=node;
        }
        if(i==j){
            return;
        }
        int k=0;
        while(inorder[x+k]!=preorder[i]){
            k++;
        }
        VLR(node, preorder, i+1, i+k, inorder, x, x+k-1, false);
        VLR(node, preorder, i+k+1, j, inorder, x+k+1, y, true);
    }

    public void flatten(TreeNode root) {
        if(root.left==null){
            return;
        }
        TreeNode rear;
        rear=root.left;
        while(rear.right!=null){
            rear=rear.right;
        }
        rear.right=root.right;
        root.right=root.left;
        root.left=null;
        flatten(root.right);
    }

    public int longestConsecutive(int[] nums) {
        HashSet<Integer> hashSet=new HashSet<Integer>();
        int ans=0;
        for(int num:nums){
            hashSet.add(num);
        }
        for(int num:nums){
            if(!hashSet.contains(num-1)){
                int count=0;
                while(hashSet.contains(num+1)){
                    num++;
                    count++;
                }
                ans=Math.max(ans, count);
            }
        }
        return ans;
    }

    public boolean wordBreak(String s, List<String> wordDict) {
        boolean[] dp=new boolean[s.length()+1];
        dp[0]=true;
        for(int i=1;i<dp.length;i++){
            for(String word:wordDict){
                if(i>=word.length()&&dp[i-word.length()]&&s.substring(i-word.length(), i).equals(word)){
                    dp[i]=true;
                }
            }
        }
        return dp[s.length()];
    }

    @Test
    public void test(){
        String s= "leetcode";
        List<String> wordDict=new ArrayList<String>();
        wordDict.add("leet");
        wordDict.add("code");
        System.out.println(wordBreak(s, wordDict)); 
    }
}

